#include <cstddef>
#include <unordered_map>
using namespace std;

class Node {
public:
  int val;
  Node *next;
  Node *random;

  Node(int _val) {
    val = _val;
    next = nullptr;
    random = nullptr;
  }
};

Node *copyRandomList(Node *head) {
  if (head == nullptr) {
    return nullptr;
  }
  Node *rtHead = nullptr;
  unordered_map<Node *, Node *> _map;
  Node *head_t = head;
  // 构建新链表节点
  while (head_t != nullptr) {
    _map[head_t] = new Node(head_t->val);
    head_t = head_t->next;
  }
  rtHead = _map[head];
  // 遍历原始链表 连接新链表
  head_t = head;
  while (head_t != nullptr) {
    Node *next = head_t->next;
    Node *random = head_t->random;
    _map[head_t]->next = next == nullptr ? nullptr : _map[next];
    _map[head_t]->random = random == nullptr ? nullptr : _map[random];
    head_t = next;
  }
  return rtHead;
}